/**
 * 题目描述:
 * 有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
 * 问最多能装入背包的总价值是多大?
 */
public class Solution {
    /**
     * 状态：F(i, j):
     *      前i个物品放入大小为j的背包中所获得的最大价值
     * 状态递推：
     *      对于第i个商品，有一种例外，装不下，两种选择，放或者不放
     *      如果装不下：此时的价值与前i-1个的价值是一样的 F(i,j) = F(i-1,j)
     *      如果可以装入：需要在两种选择中找最大的
     *      F(i, j) = max{F(i-1,j), F(i-1, j - A[i]) + V[i]}
     *      F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
     *      F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出j - A[i]的大小放第i 个商品
     * 初始化：
     *      第0行和第0列都为0，表示没有装物品时的价值都为0 F(0,j) = F(i,0) = 0
     * 返回值：F(n,m)
     * */
    public int backPack(int m, int[] A, int[] V){
        int num = A.length;
        if(m == 0 || num == 0){
            return 0;
        }
        //多加一行用于初始化
        //[num + 1]表示背包中物品数量
        //[m + 1]表示背包中剩余空间大小
        int[][] maxValue = new int[num + 1][m + 1];
        
        //初始化,第一行第一列都设为0
        for (int i = 0; i <= num; i++) {
            maxValue[i][0] = 0;
        }
        for (int i = 1; i <= m; i++) {
            maxValue[0][i] = 0;
        }
        for (int i = 1; i <= num; i++) {
            for (int j = 0; j <= m; j++) {
                //第i个商品在A中对应的索引为i-1: i从1开始
                //如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同
                if(A[i-1] > j){
                    maxValue[i][j] = maxValue[i - 1][j];
                }else{
                    //如果可以装下，分两种情况，装或者不装
                    //如果不装，则即为(i-1, j)
                    //如果装，需要腾出放第i个物品大小的空间：j - A[i-1],装入之后的最大价值即为(i - 1, j - A[i-1]) + 第i个商品的价值V[i - 1]
                    //最后在装与不装中选出最大的价值
                    int newValue = maxValue[i - 1][j - A[i - 1]] + V[i - 1];
                    maxValue[i][j] = Math.max(maxValue[i - 1][j], newValue);
                }
            }
        }
        return maxValue[num][m];
    }
    
    //优化算法
    public int backPackII(int m, int[] A, int[] V) {
        int num = A.length;
        if(m == 0 || num == 0){
            return 0;
        }
        //多加一行用于初始化

        int[] maxValue = new int[m + 1];

        //初始化,都设为0
        for (int i = 1; i <= m; i++) {
            maxValue[i] = 0;
        }
        for (int i = 1; i <= num; i++) {
            for (int j = m; j > 0; j--) {
                //第i个商品在A中对应的索引为i-1: i从1开始
                //如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同
                if(A[i-1] <= j){
                    //如果可以装下，分两种情况，装或者不装
                    //如果不装，则即为(i-1, j)
                    //如果装，需要腾出放第i个物品大小的空间：j - A[i-1],装入之后的最大价值即为(i - 1, j - A[i-1]) + 第i个商品的价值V[i - 1]
                    //最后在装与不装中选出最大的价值
                    int newValue = maxValue[j - A[i - 1]] + V[i - 1];
                    maxValue[j] = Math.max(maxValue[j], newValue);
                }
            }
        }
        return maxValue[m];
    }
}
